In the design of routers and switches, table lookup processing needs to be performed for data, so that the next node of a packet can be found. For example, in a usual routing device, after the forwarding engine receives an Internet Protocol (IP) packet, the forwarding engine extracts the destination IP address of the packet, and looks up a Forwarding Information Base (FIB) table for the index of the next-hop IP address. A table lookup rule usually applied now is the Longest Prefix Match (LPM) rule.
In the evolution from Internet Protocol version 4 (IPv4) to Internet Protocol version 6 (IPv6), there are two methods for implementing IPv6 LPM table lookup in the prior art: (i) a dedicated Ternary Content Addressable Memory (TCAM) is used to search for and find contents quickly; and (ii) a special lookup algorithm (such as a Trie algorithm or a B-tree algorithm) is used, and an off-chip cost-efficient Synchronous Dynamic Random Access Memory (SDRAM) or Static Random Access Memory (SRAM) is used for storing FIB entries. The principles of the Trie algorithm are as follows: An IP address is divided into multiple segments, and each segment is used to access an external Random Access Memory (RAM) for one time. The more bits an IP address is composed of, the more segments the IP address is divided into, and the more frequently the external RAM is accessed. The basic principles of the B-tree algorithm are as follows: A complete IP address is used to access the external RAM repeatedly, until the desired content is found.
In the process of implementing the present invention, the inventor finds that: An IPv6 address (composed of 128 bits) is composed of much more bits than an IPv4 address (composed of 32 bits); if method (i) mentioned above is adopted to implement IPv6 LPM table lookup, the number of TCAM chips need to be increased, and at present the TCAM chips are rather costly and consume power drastically; and if method (ii) mentioned above is adopted to implement IPv6 LPM table lookup, it is required to access the external RAM for much more times, which deteriorates the table lookup performance